package com.lxq.LeetCode.minSumOfLengths;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3, 2, 6, 7, 2, 1, 4, 8};
        int target = 5;
        System.out.println(minSumOfLengths(arr, target));
    }

    public static int minSumOfLengths(int[] arr, int target) {
//        if (arr.length == 1) {
//            return -1;
//        }
//        int p = 0, q = 0;
//        int[] smallSubArr = {100001, 100001};
//        int tag = target;
//        while (q < arr.length) {
//            int temp = tag - arr[q];
//            while (temp < 0) {
//                if (p < q) {
//                    tag = temp + arr[p];
//                    temp = tag;
//                    p++;
//                } else {
//                    p = ++q;
//                    if (q > arr.length - 1) {
//                        int res = smallSubArr[0] + smallSubArr[1];
//                        return res <= arr.length ? res : -1;
//                    }
//                    tag = target;
//                    temp = tag - arr[q];
//                }
//            }
//            if (temp > 0) {
//                tag = temp;
//                q++;
//            }
//            if (temp == 0) {
//                tag = target;
//
//                if (smallSubArr[0] > smallSubArr[1]) {
//                    smallSubArr[0] = Math.min(smallSubArr[0], q - p + 1);
//                } else {
//                    smallSubArr[1] = Math.min(smallSubArr[1], q - p + 1);
//                }
//
//                p = ++q;
//            }
//
//        }
//        int res = smallSubArr[0] + smallSubArr[1];
//        return res <= arr.length ? res : -1;
        int n = arr.length;
        int[] dp = new int[n];
        // 注意不能设置为最大值，因为相加会溢出
        Arrays.fill(dp, Integer.MAX_VALUE / 2);

        int ans = Integer.MAX_VALUE;
        for (int i = 0, j = 0, sum = 0; j < n; j++) {
            sum += arr[j];
            while (i <= j && sum > target) {
                sum -= arr[i++];
            }
            // 找到满足条件的一个区间
            if (sum == target) {
                dp[j] = j - i + 1;
                if (i != 0) {
                    ans = Math.min(ans, dp[i - 1] + j - i + 1);
                }
            }
            if (j != 0) {
                dp[j] = Math.min(dp[j], dp[j - 1]);
            }
        }
        return ans > arr.length ? -1 : ans;
    }
}
